#include <iostream>
#include <vector>
using namespace std;

// 用第一个元素将待排序序列划分为左右两个部分
template <typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
// 分区操作，返回中间的位置
int partiton(vector<T>& arr, int left, int right) {
    T pivot = arr[left];
    while(left < right) {
        // 左边已经是pivot了，别记录过来，那么就可以被覆盖，所以可以选择右边开始
        while (left < right && arr[right] >= pivot) right--;
        arr[left] = arr[right]; // 移动了右边，那么待会右边就可以被用于覆盖
        while (left < right && arr[left] <= pivot) left++;
        arr[right] = arr[left];
    }
    arr[left] = pivot;
    return left;
}
template<typename T>
void quickSort(vector<T>& arr, int left, int right) {
    if (left < right) {
        int mid = partiton(arr, left, right);
        quickSort(arr, left, mid-1);
        quickSort(arr, mid+1, right);
    }
}
int main()
{
  // int arr[] = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
  // int len = (int)sizeof(arr) / sizeof(*arr);
  vector<int> arr = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
  int len = arr.size();
  quickSort<int>(arr, 0, len - 1);
  for (int i = 0; i < len; i++)
    cout << arr[i] << ' ';
  cout << endl;

  float arrf[] = {17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4};
  len = (int)sizeof(arrf) / sizeof(*arrf);
  quickSort<int>(arr, 0, len - 1);
  for (int i = 0; i < len; i++)
    cout << arrf[i] << ' ' << endl;
  return 0;
}
